package leetcode.code0407;

import java.util.PriorityQueue;

public class Solution extends Solution407 {

	private PriorityQueue<int[]> edge; // 桶边
	private int x; // 原数组行数
	private int y; // 原数组列数
	boolean[][] check; // check[i][j] 表示 i,j 是否检查过

	@Override
	public int trapRainWater(int[][] heightMap) {
		x = heightMap.length;
		y = heightMap[0].length;
		check = new boolean[x][y];
		edge = new PriorityQueue<>((o1, o2) -> o1[2] - o2[2]); // 以桶边为比较的小根堆 o[0],o[1]分别是横纵坐标,o[2]是该点高度
		fillEdge(heightMap);// 将四边加入桶边
		int ans = 0; // 答案
		while (!edge.isEmpty()) {
			int[] low = edge.poll(); // 弹出最小桶边, 木桶原理
			ans += infectFrom(heightMap, low[0], low[1], low[2]);// 从low开始感染
		}
		return ans;
	}

	private int infectFrom(int[][] heightMap, int x, int y, int low) {
		int ans = 0;
		ans += this.infectHere(heightMap, x + 1, y, low);// 感染上
		ans += this.infectHere(heightMap, x - 1, y, low);// 感染下
		ans += this.infectHere(heightMap, x, y + 1, low);// 感染右
		ans += this.infectHere(heightMap, x, y - 1, low);// 感染左
		return ans;
	}

	private int infectHere(int[][] heightMap, int row, int col, int low) {
		int ans = 0;
		if (this.canBeInfect(row, col)) {// 这个位置是否能感染
			int height = 0;
			if ((height = heightMap[row][col]) < low) {// 小于桶边就结算高度继续感染
				ans += (low - height);
				ans += this.infectFrom(heightMap, row, col, low);// 沿用最小桶边
			} else {// 大于桶边就添加到边, 停止感染
				edge.add(new int[] { row, col, heightMap[row][col] });
			}
		}
		return ans;
	}

	private boolean canBeInfect(int row, int col) {
		// 没越界, 没查过的 , 才可以感染
		if (row >= 0 && col >= 0 && row < x && col < y && !check[row][col]) {
			check[row][col] = true;
			return true;
		}
		return false;
	}

	private void fillEdge(int[][] heightMap) {
		for (int i = 0; i < y - 1; i++) {// 上
			edge.add(new int[] { 0, i, heightMap[0][i] });
			check[0][i] = true;
		}
		for (int i = 0; i < x - 1; i++) {// 右
			edge.add(new int[] { i, y - 1, heightMap[i][y - 1] });
			check[i][y - 1] = true;
		}
		for (int i = y - 1; i > 0; i--) {// 下
			edge.add(new int[] { x - 1, i, heightMap[x - 1][i] });
			check[x - 1][i] = true;
		}
		for (int i = x - 1; i > 0; i--) {
			edge.add(new int[] { i, 0, heightMap[i][0] });
			check[i][0] = true;
		}
	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
	}

}
